Skip to main content

Merge K Sorted Arrays

Problem Description​

Given k sorted arrays arranged in the form of a matrix of size k * k. The task is to merge them into one sorted array. Return the merged sorted array

Examples​

Example 1:

Input: k = 3, arr[][] = {{1,2,3},{4,5,6},{7,8,9}}
Output: 1 2 3 4 5 6 7 8 9
Explanation: Above test case has 3 sorted arrays of size 3, 3, 3 arr[][] = [[1, 2, 3],[4, 5, 6],[7, 8, 9]]. The merged list will be [1, 2, 3, 4, 5, 6, 7, 8, 9].

Example 2:

Input: k = 4, arr[][]={{1,2,3,4},{2,2,3,4},{5,5,6,6},{7,8,9,9}}
Output: 1 2 2 2 3 3 4 4 5 5 6 6 7 8 9 9
Explanation: Above test case has 4 sorted arrays of size 4, 4, 4, 4 arr[][] = [[1, 2, 2, 2], [3, 3, 4, 4], [5, 5, 6, 6], [7, 8, 9, 9 ]]. The merged list will be [1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9].

Constraints​

  • 1 <= k <= 100

Problem Explanation​

Given k sorted arrays arranged in the form of a matrix of size k * k. The task is to merge them into one sorted array. Return the merged sorted array

Code Implementation​

C++ Solution​

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> mergeSortedArrays(std::vector<std::vector<int>> arrays) {
std::vector<int> result;
for (const auto& array : arrays) {
result.insert(result.end(), array.begin(), array.end());
}
std::sort(result.begin(), result.end());
return result;
}

int main() {
std::vector<std::vector<int>> arrays = { { 1, 3, 5 }, { 2, 4, 6 }, { 0, 7, 8 } };
std::vector<int> result = mergeSortedArrays(arrays);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}




import java.util.Arrays;

public class Main {
public static void main(String[] args) {
int[][] arrays = { { 1, 3, 5 }, { 2, 4, 6 }, { 0, 7, 8 } };
int[] result = mergeSortedArrays(arrays);
System.out.println(Arrays.toString(result));
}

public static int[] mergeSortedArrays(int[][] arrays) {
int[] result = new int[arrays.length * arrays[0].length];
int index = 0;
for (int[] array : arrays) {
for (int num : array) {
result[index++] = num;
}
}
Arrays.sort(result);
return result;
}
}


import itertools

def merge_sorted_arrays(arrays):
return sorted(itertools.chain(*arrays))


function mergeSortedArrays(arrays) {
return arrays.flat().sort((a, b) => a - b);
}


Solution Logic:​

  1. Flatten the 2D array:
    • Iterate through each subarray in the 2D array.
    • Concatenate each subarray to a single array.
  2. Sort the 1D array:
    • Use a sorting algorithm (e.g. quicksort, mergesort) to sort the array in ascending order.
  3. Return the sorted 1D array:
    • Return the sorted array as the final result.

Time Complexity​

  • The time complexity is O(n∗log(n))O(n*log(n)) where n is the total number of elements in the arrays.

Space Complexity​

  • O(n)O(n) where n is the total number of elements in the arrays.